wallet: Make IsTrusted scan parents recursively #16766

JeremyRubin · 2019-08-30T19:45:43Z

This slightly modifies the behavior of IsTrusted to recursively check the parents of a transaction. Otherwise, it's possible that a parent is not IsTrusted but a child is. If a parent is not trusted, then a child should not be either.

This recursive scan can be a little expensive, so ~~it might be beneficial to have a way of caching IsTrusted state, but this is a little complex because various conditions can change between calls to IsTrusted (e.g., re-org).~~ I added a cache which works per call/across calls, but does not store the results semi-permanently. Which reduces DoS risk of this change. There is no risk of untrusted parents causing a resource exploitation, as we immediately return once that is detected.

This is a change that came up as a bug-fix esque change while working on OP_SECURETHEBAG. You can see the branch where this change is important here: https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:stb-with-rpc?expand=1. Essentially, without this change, we can be tricked into accepting an OP_SECURETHEBAG output because we don't properly check the parents. As this was a change which, on its own, was not dependent on OP_SECURETHEBAG, I broke it out as I felt the change stands on its own by fixing a long standing wallet bug.

The test wallet_balance.py has been corrected to meet the new behavior. The below comment, reproduced, explains what the issue is and the edge cases that can arise before this change.

    # Before `test_balance()`, we have had two nodes with a balance of 50
    # each and then we:
    #
    # 1) Sent 40 from node A to node B with fee 0.01
    # 2) Sent 60 from node B to node A with fee 0.01
    #
    # Then we check the balances:
    #
    # 1) As is
    # 2) With transaction 2 from above with 2x the fee
    #
    # Prior to #16766, in this situation, the node would immediately report
    # a balance of 30 on node B as unconfirmed and trusted.
    #
    # After #16766, we show that balance as unconfirmed.
    #
    # The balance is indeed "trusted" and "confirmed" insofar as removing
    # the mempool transactions would return at least that much money. But
    # the algorithm after #16766 marks it as unconfirmed because the 'taint'
    # tracking of transaction trust for summing balances doesn't consider
    # which inputs belong to a user. In this case, the change output in
    # question could be "destroyed" by replace the 1st transaction above.
    #
    # The post #16766 behavior is correct; we shouldn't be treating those
    # funds as confirmed. If you want to rely on that specific UTXO existing
    # which has given you that balance, you cannot, as a third party
    # spending the other input would destroy that unconfirmed.
    #
    # For example, if the test transactions were:
    #
    # 1) Sent 40 from node A to node B with fee 0.01
    # 2) Sent 10 from node B to node A with fee 0.01
    #
    # Then our node would report a confirmed balance of 40 + 50 - 10 = 80
    # BTC, which is more than would be available if transaction 1 were
    # replaced.

The release notes have been updated to note the new behavior.

JeremyRubin · 2019-08-30T20:37:32Z

I added a cache which works per call/across calls, but does not store the results semi-permanently.

This should reduce DoS risk of this change.

There is no risk of untrusted parents causing a resource exploitation, as we immediately return once that is detected.

DrahtBot · 2019-08-30T22:33:01Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#15931 (Remove GetDepthInMainChain dependency on locked chain interface by ariard)
#15729 (rpc: Raise error in getbalance if minconf is not zero by promag)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

maflcko · 2019-09-03T15:48:00Z

If a parent is not trusted, then a child should not be either.

Would be nice to have a test for this or update the wallet_balance.py script in case it is already tested there. (wallet_balance.py is failing)

JeremyRubin · 2019-09-03T17:42:37Z

I updated the tests to pass.

In the test, we have two nodes with a balance of 50 each and then:

Send 40 from node A to node B.
Send 60 from node B to node A.

Then we would check the balances.

Previously, we would immediately report a balance of 30 on node B as unconfirmed and trusted.

Now, we show that balance as unconfirmed.

The balance is indeed "trusted" and "confirmed" insofar as removing the mempool transactions would return at least that much money. But the current software marks it as unconfirmed because the 'taint' tracking of transaction trust for summing balances doesn't consider which inputs belong to a user.

I think the new behavior is correct; we shouldn't be treating those funds as confirmed. If you want to rely on that specific UTXO existing which has given you that balance, you cannot, as a third party spending the other input would destroy that unconfirmed.

Overall I think that this points to a general concept worth exploring as a revision to the categories "unconfirmed" and "confirmed", to have "free cash", "locked", and "unconfirmed". Free cash can be spent at will, locked funds are balances that are guaranteed to exist but we don't have a confirmed UTXO for yet, and unconfirmed are funds we may or may not receive. I think this is out of scope of this PR though, but is worth further thought.

maflcko

Concept ACK

test/functional/wallet_balance.py

JeremyRubin · 2019-09-05T18:47:57Z

Test failure unrelated it seems? In assumevalid

jonatack

Concept ACK.

Test failure unrelated it seems? In assumevalid

Yup, just built and all tests are green.

promag · 2019-09-05T23:47:40Z

src/wallet/wallet.cpp

        for (const auto& entry : mapWallet)
        {
            const CWalletTx& wtx = entry.second;
-            const bool is_trusted{wtx.IsTrusted(*locked_chain)};
+            const bool is_trusted{wtx.IsTrusted(*locked_chain, trustedParents)};


With the overloaded IsTrusted this could be reverted? Same below.

Nope -- because I'm caching the trust across the entire wallet (outside the loop) rather than just a single call.

Right, missed this is in a loop 🤦‍♂

promag · 2019-09-05T23:51:38Z

src/wallet/wallet.cpp

        if (pwallet->IsMine(parentOut) != ISMINE_SPENDABLE)
            return false;
+        // If we've already trusted this parent, continue
+        if (trustedParents.count(parent->GetHash()))
+            continue;


nit, join with line above - to follow correct format.

Not sure what you mean

got it; went ahead and did this in the entire function (rather than leave it half-styled)

Yup, that was the idea.

promag · 2019-09-05T23:51:48Z

src/wallet/wallet.cpp

+    return IsTrusted(locked_chain, s);
+}
+
+bool CWalletTx::IsTrusted(interfaces::Chain::Lock& locked_chain, std::set<uint256>& trustedParents) const


nit, snake case - header too.

Did we change styles?

We settled on a variable naming style in 2017: 47d8441

promag · 2019-09-06T16:52:00Z

Do you expect a performance penalty for big wallets?

JeremyRubin · 2019-09-06T17:26:42Z

Yes and No.

Yes:
A properly constructed wallet, which has long-chains of unconfirmed transactions, will take longer to analyze. However, given the use of the set cache it should still be linear in the number of long-chain inputs (this could be large if there are a ton of fully independent unconfirmeds being spent).

No:
A normal wallet, and normal wallet transactions (who is confirmed or whose parents are all confirmed) won't have much impact. Note we also abort as soon as we find an offending tx. It might be better to do this via BFS than DFS, but DFS is simpler to implement.

Note that a third party can't force a long-chain lookup on you without your participation, because you're checking IsMine at each level. So an unconfirmed spend to you will look back only until it's a transaction with another participant that's unconfirmed.

It's also possible to use an unordered_set here -- but perhaps that's better done as something across the module (std::set/map is used extensively)

promag

@JeremyRubin thanks for the detailed response! Some comments follow.

promag · 2019-09-13T11:42:07Z

src/wallet/wallet.cpp

-    if (!locked_chain.checkFinalTx(*tx)) {
-        return false;
-    }
+    if (!locked_chain.checkFinalTx(*tx)) return false;
    int nDepth = GetDepthInMainChain(locked_chain);


Maybe I'm missing something but I think you could avoid calling GetDepthInMainChain for parents if nDepth >= 1?

You're right, but we already don't recurse on trusted parents right?

promag · 2019-09-13T11:44:26Z

src/wallet/wallet.h

@@ -576,6 +576,7 @@ class CWalletTx

    bool InMempool() const;
    bool IsTrusted(interfaces::Chain::Lock& locked_chain) const;
+    bool IsTrusted(interfaces::Chain::Lock& locked_chain, std::set<uint256>& trusted_parents) const;


nit, should be private?

Actually I'd rather just get rid of the other function as usually you'd want to share the cache across IsTrusted calls...

Slightly more agressive change but maybe it's ok

promag · 2019-09-13T11:51:21Z

src/wallet/wallet.cpp

+        // Check that this specific input being spent is trusted
+        if (pwallet->IsMine(parentOut) != ISMINE_SPENDABLE) return false;
+        // If we've already trusted this parent, continue
+        if (trusted_parents.count(parent->GetHash())) continue;


You could .insert() here, and use the result value .second to know whether it was missing and then call parent->IsTrusted.

I'm a little uncomfortable with that design because we then need to remove ourselves from the set if the recursion returns false.

It's also a bit weird because we add ourselves to the trusted set before recursion so technically there are elements not known to be trusted in the set. This is safe because the element is a child, but it's odd.

luke-jr · 2019-09-20T21:41:03Z

I think the new behavior is correct; we shouldn't be treating those funds as confirmed. If you want to rely on that specific UTXO existing which has given you that balance, you cannot, as a third party spending the other input would destroy that unconfirmed.

But your balance isn't specific UTXOs. Users don't care about UTXOs, just total bitcoins.

30 BTC should show as confirmed and trusted...

JeremyRubin · 2019-09-21T08:16:30Z

Then it's a mistake to compute balance from summing IsTrusted, but we shouldn't rely on broken IsTrusted behavior to compute Balance.

Bear in mind for the specific situation you're thinking of, there are also edge cases where we over report correct balance.

fjahr · 2019-10-01T08:40:46Z

Otherwise, it's possible that a parent is not IsTrusted but a child is.

Was the test you changed a good example of how this can happen or did you have other examples in mind? Would it be worth to have an explicit test for that?

fjahr · 2019-10-01T08:43:50Z

src/wallet/wallet.cpp

        for (const auto& entry : mapWallet)
        {
            const CWalletTx& wtx = entry.second;
-            const bool is_trusted{wtx.IsTrusted(*locked_chain)};
+            const bool is_trusted{wtx.IsTrusted(*locked_chain, trusted_parents)};


nit: I would prefer to keep using the old interface here and in 2488, 3784 until the trusted_parents are actually used/shared.

What do you mean by "actually used/shared"?

I mean for now, you could leave this line unchanged since trusted_parents is not used outside of IsTrusted. I know you eventually want to share the parents for optimization but I would not change this line until that is the case.

I'm not sure what the "eventually" or "actually" part is... this is what is done by the code already. Note that trusted_parents lives outside the for loop so is shared across calls.

And it's less so optimization and more so anti-DoS.

I see, I misunderstood at which level the caching is happening, thanks!

ryanofsky

Code review ACK 58cb227. This seems right. It doesn't seem good to trust a child transaction if the parents aren't trusted. But I don't understand what originally motivated this change. Is there a prototypical example of a case where this would be an obvious improvement? The test example in #16766 (comment) seems more like arguably correct behavior with not a great outcome. I wouldn't mind seeing:

The PR description updated with more motivation, and maybe a motivating example
A release note to warn users and avoid surprises from balances being computed differently than before

I like the proposed free/locked/unconfirmed idea, too. I hope future changes could allow figuring out a free+locked value, which has seemed to me like a useful thing to have before #15010 (comment).

ryanofsky · 2019-10-21T18:56:50Z

test/functional/wallet_balance.py

@@ -112,10 +112,10 @@ def run_test(self):
        def test_balances(*, fee_node_1=0):


In commit "Update wallet_balance.py test to reflect new behavior" (bee1dc9)

You also have a really nice description of the test setup in #16766 (comment) that could be nice to incorporate as a comment or link in the test_balances function.

JeremyRubin · 2019-10-21T20:11:51Z

Hi @ryanofsky, thanks for the review!

This is a change that came up as a bug-fix esque change while working on OP_SECURETHEBAG. You can see the branch where this change is important here: https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:stb-with-rpc?expand=1. Essentially, without this change, we can be tricked into accepting an OP_SECURETHEBAG output because we don't properly check the parents.

As this was a change which, on its own, was not dependent on OP_SECURETHEBAG, I broke it out as I felt the change stands on its own.

I'll add to the release notes and to the tests comments.

Co-Authored-By: MarcoFalke <falke.marco@gmail.com>

…llet

JeremyRubin · 2019-10-21T20:51:34Z

I had to rebase to clear out the release notes; code hasn't changed except the comment in wallet_balances.py. I have also updated the PR message.

re-ack when you have a moment @ryanofsky!

ryanofsky

Code review ACK 4671fc3. Changes since last review: 2 new commits adding suggested release note and python test comment, also a clean rebase with no changes to the earlier commits. The PR description is more comprehensive now, too. Looks good!

ariard

Concept ACK, this was previously a non-tested bug. Don't know about the DoS protection, see comment.

Overall I think that this points to a general concept worth exploring as a revision to the categories "unconfirmed" and "confirmed", to have "free cash", "locked", and "unconfirmed". Free cash can be spent at will, locked funds are balances that are guaranteed to exist but we don't have a confirmed UTXO for yet, and unconfirmed are funds we may or may not receive. I think this is out of scope of this PR though, but is worth further thought

Agree, UTXO state management is pretty unclear currently, I was thinking about this on the spending-side to rework abandontransaction to something like abandonutxo with the given nomenclature, committed UTXO included in one or more tx, spent UTXO include in a confirm tx, where user should be able to unlock committed UTXO if they are his. Conflicts tracking should stay at the transaction-level. On the receiving-side, not sure about the difference between locked and unconfirmed

ariard · 2019-10-24T21:00:42Z

src/wallet/wallet.cpp

@@ -2294,6 +2294,12 @@ bool CWalletTx::InMempool() const
 }

 bool CWalletTx::IsTrusted(interfaces::Chain::Lock& locked_chain) const
+{
+    std::set<uint256> s;


Hmm I don't know about the need of DoS protection, can't we rely on mempool DEFAULT_ANCESTOR_LIMIT there ? A transaction to be trusted has to be in-mempool (among other standards), so their unconfirmed parent too, at first parent hit which is not we should return. What's th worst complexity for a graph of 25 parents?

Even so, you can imagine a case where we have a single input single output chain of 25 taking:

sum n = 0 to N n = n * (n-1) /2 = O(N^2).

Which for 25 = 625 iterations.

Imagine what this would be for a tree with no descendants limit!

The caching guarantees that it is O(N*log(N)) worst case (could be improved possibly by switching to unordered_set... but it's worth benchmarking since we will usually have a very small set)

I believe the worst case is O(a^n), where a is the number of inputs/output per transaction, and n is the ancestor limit. Simply build a tx graph where every transaction spends a outputs of the previous layer, in a different inputs.

Okay assuming complexity O(a^n), standard txn are limited by MAX_STANDARD_TX_WEIGHT and 148-bytes input, that gives you 548 inputs/outputs on every tx layer so something like 13700 iterations... Would be interesting to know how IsTrusted behaves on such computation order, but the fees burn for a DoS attacker seems pretty high.

Imagine what this would be for a tree with no descendants limit!

Not sure why descendants limit matters there?

Anyway, DoS protection is simple enough to get it for peace of mind.

ariard · 2019-10-24T21:02:23Z

src/wallet/wallet.cpp

@@ -2420,10 +2420,11 @@ CWallet::Balance CWallet::GetBalance(const int min_depth, bool avoid_reuse) cons
    {
        auto locked_chain = chain().lock();
        LOCK(cs_wallet);
+        std::set<uint256> trustedParents;


If you go with DoS protection, can't you go further and reuse the cached set of trusted parents between WalletTxToJSON call in listtransactions and listsinceblock, they are all after chain locks so shouldn't be an issue ?

Possibly, but because it's through the interfaced call I didn't want to scope creep to include that. But it's maybe worth a follow up PR?

Really IMO but if DoS protection is worth it, it should take precedence on creeping into interfaced call.

ariard · 2019-10-24T21:07:23Z

doc/release-notes.md

@@ -85,6 +85,7 @@ Wallet
 ------

 - The wallet now by default uses bech32 addresses when using RPC, and creates native segwit change outputs.
+- The way that output trust was computed has been fixed in #16766, which impacts confirmed/unconfirmed balance status and coin selection.


nit: maybe precise how the trust computation has been changed "to evaluate trustiness of outpoint spent by parent and so recursively"

I'm not sure what level of detail is best for the release note; will leave up to maintainer discretion. Since it can be nuanced, if someone is relying on this it's best that they read the PR.

ariard · 2019-10-25T17:17:31Z

Code Review ACK 4671fc3, maybe extend DoS protection in a follow-up PR.

fjahr · 2019-10-30T21:24:02Z

Code review ACK 4671fc3

Thanks for adding the extended description in the test. Good idea @ryanofsky !

promag

Code review ACK 4671fc3.

b49dcbe could be avoided (by fixing the respective commits in the first place) and 8f174ef could be discarded since it's kind of unrelated. I guess it's not a big deal considering the existing ACK.

Looking into IsTrusted, couldn't we change it to not require cs_main (just cs_wallet)?

4671fc3 Expand on wallet_balance.py comment from #16766 (Jeremy Rubin) 91f3073 Update release notes to mention changes to IsTrusted and impact on wallet (Jeremy Rubin) 8f174ef Systematize style of IsTrusted single line if (Jeremy Rubin) b49dcbe update variable naming conventions for IsTrusted (Jeremy Rubin) 5ffe0d1 Update comment in test/functional/wallet_balance.py (Jeremy Rubin) a550c58 Update wallet_balance.py test to reflect new behavior (Jeremy Rubin) 5dd7da4 Reuse trustedParents in looped calls to IsTrusted (Jeremy Rubin) 595f09d Cache tx Trust per-call to avoid DoS (Jeremy Rubin) dce032c Make IsTrusted scan parents recursively (Jeremy Rubin) Pull request description: This slightly modifies the behavior of IsTrusted to recursively check the parents of a transaction. Otherwise, it's possible that a parent is not IsTrusted but a child is. If a parent is not trusted, then a child should not be either. This recursive scan can be a little expensive, so ~it might be beneficial to have a way of caching IsTrusted state, but this is a little complex because various conditions can change between calls to IsTrusted (e.g., re-org).~ I added a cache which works per call/across calls, but does not store the results semi-permanently. Which reduces DoS risk of this change. There is no risk of untrusted parents causing a resource exploitation, as we immediately return once that is detected. This is a change that came up as a bug-fix esque change while working on OP_SECURETHEBAG. You can see the branch where this change is important here: https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:stb-with-rpc?expand=1. Essentially, without this change, we can be tricked into accepting an OP_SECURETHEBAG output because we don't properly check the parents. As this was a change which, on its own, was not dependent on OP_SECURETHEBAG, I broke it out as I felt the change stands on its own by fixing a long standing wallet bug. The test wallet_balance.py has been corrected to meet the new behavior. The below comment, reproduced, explains what the issue is and the edge cases that can arise before this change. # Before `test_balance()`, we have had two nodes with a balance of 50 # each and then we: # # 1) Sent 40 from node A to node B with fee 0.01 # 2) Sent 60 from node B to node A with fee 0.01 # # Then we check the balances: # # 1) As is # 2) With transaction 2 from above with 2x the fee # # Prior to #16766, in this situation, the node would immediately report # a balance of 30 on node B as unconfirmed and trusted. # # After #16766, we show that balance as unconfirmed. # # The balance is indeed "trusted" and "confirmed" insofar as removing # the mempool transactions would return at least that much money. But # the algorithm after #16766 marks it as unconfirmed because the 'taint' # tracking of transaction trust for summing balances doesn't consider # which inputs belong to a user. In this case, the change output in # question could be "destroyed" by replace the 1st transaction above. # # The post #16766 behavior is correct; we shouldn't be treating those # funds as confirmed. If you want to rely on that specific UTXO existing # which has given you that balance, you cannot, as a third party # spending the other input would destroy that unconfirmed. # # For example, if the test transactions were: # # 1) Sent 40 from node A to node B with fee 0.01 # 2) Sent 10 from node B to node A with fee 0.01 # # Then our node would report a confirmed balance of 40 + 50 - 10 = 80 # BTC, which is more than would be available if transaction 1 were # replaced. The release notes have been updated to note the new behavior. ACKs for top commit: ariard: Code Review ACK 4671fc3, maybe extend DoS protection in a follow-up PR. fjahr: Code review ACK 4671fc3 ryanofsky: Code review ACK 4671fc3. Changes since last review: 2 new commits adding suggested release note and python test comment, also a clean rebase with no changes to the earlier commits. The PR description is more comprehensive now, too. Looks good! promag: Code review ACK 4671fc3. Tree-SHA512: 6b183ff425304fef49724290053514cb2770f4a2350dcb83660ef24af5c54f7c4c2c345b0f62bba60eb2d2f70625ee61a7fab76a7f491bb5a84be5c4cc86b92f

meshcollider · 2019-11-05T08:59:41Z

Concept ACK, this looks ready with 4 review ACKs

ryanofsky · 2019-11-05T18:20:21Z

re: #16766 (review) from @promag

Looking into IsTrusted, couldn't we change it to not require cs_main (just cs_wallet)?

It's not trivial because of the GetDepthInMainChain and checkFinalTx calls, but #16426 does this

4671fc3 Expand on wallet_balance.py comment from bitcoin#16766 (Jeremy Rubin) 91f3073 Update release notes to mention changes to IsTrusted and impact on wallet (Jeremy Rubin) 8f174ef Systematize style of IsTrusted single line if (Jeremy Rubin) b49dcbe update variable naming conventions for IsTrusted (Jeremy Rubin) 5ffe0d1 Update comment in test/functional/wallet_balance.py (Jeremy Rubin) a550c58 Update wallet_balance.py test to reflect new behavior (Jeremy Rubin) 5dd7da4 Reuse trustedParents in looped calls to IsTrusted (Jeremy Rubin) 595f09d Cache tx Trust per-call to avoid DoS (Jeremy Rubin) dce032c Make IsTrusted scan parents recursively (Jeremy Rubin) Pull request description: This slightly modifies the behavior of IsTrusted to recursively check the parents of a transaction. Otherwise, it's possible that a parent is not IsTrusted but a child is. If a parent is not trusted, then a child should not be either. This recursive scan can be a little expensive, so ~it might be beneficial to have a way of caching IsTrusted state, but this is a little complex because various conditions can change between calls to IsTrusted (e.g., re-org).~ I added a cache which works per call/across calls, but does not store the results semi-permanently. Which reduces DoS risk of this change. There is no risk of untrusted parents causing a resource exploitation, as we immediately return once that is detected. This is a change that came up as a bug-fix esque change while working on OP_SECURETHEBAG. You can see the branch where this change is important here: https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:stb-with-rpc?expand=1. Essentially, without this change, we can be tricked into accepting an OP_SECURETHEBAG output because we don't properly check the parents. As this was a change which, on its own, was not dependent on OP_SECURETHEBAG, I broke it out as I felt the change stands on its own by fixing a long standing wallet bug. The test wallet_balance.py has been corrected to meet the new behavior. The below comment, reproduced, explains what the issue is and the edge cases that can arise before this change. # Before `test_balance()`, we have had two nodes with a balance of 50 # each and then we: # # 1) Sent 40 from node A to node B with fee 0.01 # 2) Sent 60 from node B to node A with fee 0.01 # # Then we check the balances: # # 1) As is # 2) With transaction 2 from above with 2x the fee # # Prior to bitcoin#16766, in this situation, the node would immediately report # a balance of 30 on node B as unconfirmed and trusted. # # After bitcoin#16766, we show that balance as unconfirmed. # # The balance is indeed "trusted" and "confirmed" insofar as removing # the mempool transactions would return at least that much money. But # the algorithm after bitcoin#16766 marks it as unconfirmed because the 'taint' # tracking of transaction trust for summing balances doesn't consider # which inputs belong to a user. In this case, the change output in # question could be "destroyed" by replace the 1st transaction above. # # The post bitcoin#16766 behavior is correct; we shouldn't be treating those # funds as confirmed. If you want to rely on that specific UTXO existing # which has given you that balance, you cannot, as a third party # spending the other input would destroy that unconfirmed. # # For example, if the test transactions were: # # 1) Sent 40 from node A to node B with fee 0.01 # 2) Sent 10 from node B to node A with fee 0.01 # # Then our node would report a confirmed balance of 40 + 50 - 10 = 80 # BTC, which is more than would be available if transaction 1 were # replaced. The release notes have been updated to note the new behavior. ACKs for top commit: ariard: Code Review ACK 4671fc3, maybe extend DoS protection in a follow-up PR. fjahr: Code review ACK 4671fc3 ryanofsky: Code review ACK 4671fc3. Changes since last review: 2 new commits adding suggested release note and python test comment, also a clean rebase with no changes to the earlier commits. The PR description is more comprehensive now, too. Looks good! promag: Code review ACK 4671fc3. Tree-SHA512: 6b183ff425304fef49724290053514cb2770f4a2350dcb83660ef24af5c54f7c4c2c345b0f62bba60eb2d2f70625ee61a7fab76a7f491bb5a84be5c4cc86b92f

Summary: Expand on wallet_balance.py comment from bitcoin/bitcoin#16766 (Jeremy Rubin) Update release notes to mention changes to IsTrusted and impact on wallet (Jeremy Rubin) Systematize style of IsTrusted single line if (Jeremy Rubin) update variable naming conventions for IsTrusted (Jeremy Rubin) Update comment in test/functional/wallet_balance.py (Jeremy Rubin) Update wallet_balance.py test to reflect new behavior (Jeremy Rubin) Reuse trustedParents in looped calls to IsTrusted (Jeremy Rubin) Cache tx Trust per-call to avoid DoS (Jeremy Rubin) Make IsTrusted scan parents recursively (Jeremy Rubin) Pull request description: This slightly modifies the behavior of IsTrusted to recursively check the parents of a transaction. Otherwise, it's possible that a parent is not IsTrusted but a child is. If a parent is not trusted, then a child should not be either. This recursive scan can be a little expensive, so ~it might be beneficial to have a way of caching IsTrusted state, but this is a little complex because various conditions can change between calls to IsTrusted (e.g., re-org).~ I added a cache which works per call/across calls, but does not store the results semi-permanently. Which reduces DoS risk of this change. There is no risk of untrusted parents causing a resource exploitation, as we immediately return once that is detected. This is a change that came up as a bug-fix esque change while working on OP_SECURETHEBAG. You can see the branch where this change is important here: https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:stb-with-rpc?expand=1. Essentially, without this change, we can be tricked into accepting an OP_SECURETHEBAG output because we don't properly check the parents. As this was a change which, on its own, was not dependent on OP_SECURETHEBAG, I broke it out as I felt the change stands on its own by fixing a long standing wallet bug. The test wallet_balance.py has been corrected to meet the new behavior. The below comment, reproduced, explains what the issue is and the edge cases that can arise before this change. # Before `test_balance()`, we have had two nodes with a balance of 50 # each and then we: # # 1) Sent 40 from node A to node B with fee 0.01 # 2) Sent 60 from node B to node A with fee 0.01 # # Then we check the balances: # # 1) As is # 2) With transaction 2 from above with 2x the fee # # Prior to #16766, in this situation, the node would immediately report # a balance of 30 on node B as unconfirmed and trusted. # # After #16766, we show that balance as unconfirmed. # # The balance is indeed "trusted" and "confirmed" insofar as removing # the mempool transactions would return at least that much money. But # the algorithm after #16766 marks it as unconfirmed because the 'taint' # tracking of transaction trust for summing balances doesn't consider # which inputs belong to a user. In this case, the change output in # question could be "destroyed" by replace the 1st transaction above. # # The post #16766 behavior is correct; we shouldn't be treating those # funds as confirmed. If you want to rely on that specific UTXO existing # which has given you that balance, you cannot, as a third party # spending the other input would destroy that unconfirmed. # # For example, if the test transactions were: # # 1) Sent 40 from node A to node B with fee 0.01 # 2) Sent 10 from node B to node A with fee 0.01 # # Then our node would report a confirmed balance of 40 + 50 - 10 = 80 # BTC, which is more than would be available if transaction 1 were # replaced. The release notes have been updated to note the new behavior. --- Backport of Core [[bitcoin/bitcoin#16766 | PR16766]] Test Plan: ninja check check-functional Reviewers: #bitcoin_abc, jasonbcox Reviewed By: #bitcoin_abc, jasonbcox Subscribers: jasonbcox Differential Revision: https://reviews.bitcoinabc.org/D7695

4671fc3 Expand on wallet_balance.py comment from bitcoin#16766 (Jeremy Rubin) 91f3073 Update release notes to mention changes to IsTrusted and impact on wallet (Jeremy Rubin) 8f174ef Systematize style of IsTrusted single line if (Jeremy Rubin) b49dcbe update variable naming conventions for IsTrusted (Jeremy Rubin) 5ffe0d1 Update comment in test/functional/wallet_balance.py (Jeremy Rubin) a550c58 Update wallet_balance.py test to reflect new behavior (Jeremy Rubin) 5dd7da4 Reuse trustedParents in looped calls to IsTrusted (Jeremy Rubin) 595f09d Cache tx Trust per-call to avoid DoS (Jeremy Rubin) dce032c Make IsTrusted scan parents recursively (Jeremy Rubin) Pull request description: This slightly modifies the behavior of IsTrusted to recursively check the parents of a transaction. Otherwise, it's possible that a parent is not IsTrusted but a child is. If a parent is not trusted, then a child should not be either. This recursive scan can be a little expensive, so ~it might be beneficial to have a way of caching IsTrusted state, but this is a little complex because various conditions can change between calls to IsTrusted (e.g., re-org).~ I added a cache which works per call/across calls, but does not store the results semi-permanently. Which reduces DoS risk of this change. There is no risk of untrusted parents causing a resource exploitation, as we immediately return once that is detected. This is a change that came up as a bug-fix esque change while working on OP_SECURETHEBAG. You can see the branch where this change is important here: https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:stb-with-rpc?expand=1. Essentially, without this change, we can be tricked into accepting an OP_SECURETHEBAG output because we don't properly check the parents. As this was a change which, on its own, was not dependent on OP_SECURETHEBAG, I broke it out as I felt the change stands on its own by fixing a long standing wallet bug. The test wallet_balance.py has been corrected to meet the new behavior. The below comment, reproduced, explains what the issue is and the edge cases that can arise before this change. # Before `test_balance()`, we have had two nodes with a balance of 50 # each and then we: # # 1) Sent 40 from node A to node B with fee 0.01 # 2) Sent 60 from node B to node A with fee 0.01 # # Then we check the balances: # # 1) As is # 2) With transaction 2 from above with 2x the fee # # Prior to bitcoin#16766, in this situation, the node would immediately report # a balance of 30 on node B as unconfirmed and trusted. # # After bitcoin#16766, we show that balance as unconfirmed. # # The balance is indeed "trusted" and "confirmed" insofar as removing # the mempool transactions would return at least that much money. But # the algorithm after bitcoin#16766 marks it as unconfirmed because the 'taint' # tracking of transaction trust for summing balances doesn't consider # which inputs belong to a user. In this case, the change output in # question could be "destroyed" by replace the 1st transaction above. # # The post bitcoin#16766 behavior is correct; we shouldn't be treating those # funds as confirmed. If you want to rely on that specific UTXO existing # which has given you that balance, you cannot, as a third party # spending the other input would destroy that unconfirmed. # # For example, if the test transactions were: # # 1) Sent 40 from node A to node B with fee 0.01 # 2) Sent 10 from node B to node A with fee 0.01 # # Then our node would report a confirmed balance of 40 + 50 - 10 = 80 # BTC, which is more than would be available if transaction 1 were # replaced. The release notes have been updated to note the new behavior. ACKs for top commit: ariard: Code Review ACK 4671fc3, maybe extend DoS protection in a follow-up PR. fjahr: Code review ACK 4671fc3 ryanofsky: Code review ACK 4671fc3. Changes since last review: 2 new commits adding suggested release note and python test comment, also a clean rebase with no changes to the earlier commits. The PR description is more comprehensive now, too. Looks good! promag: Code review ACK 4671fc3. Tree-SHA512: 6b183ff425304fef49724290053514cb2770f4a2350dcb83660ef24af5c54f7c4c2c345b0f62bba60eb2d2f70625ee61a7fab76a7f491bb5a84be5c4cc86b92f

DrahtBot added the Wallet label Aug 30, 2019

maflcko changed the title ~~Make IsTrusted scan parents recursively~~ wallet: Make IsTrusted scan parents recursively Sep 3, 2019

maflcko reviewed Sep 3, 2019

View reviewed changes

test/functional/wallet_balance.py Outdated Show resolved Hide resolved

laanwj added this to Blockers in High-priority for review Sep 5, 2019

jonatack reviewed Sep 5, 2019

View reviewed changes

promag reviewed Sep 5, 2019

View reviewed changes

promag reviewed Sep 13, 2019

View reviewed changes

fjahr reviewed Oct 1, 2019

View reviewed changes

ryanofsky approved these changes Oct 21, 2019

View reviewed changes

JeremyRubin and others added 9 commits October 21, 2019 13:16

Make IsTrusted scan parents recursively

dce032c

Cache tx Trust per-call to avoid DoS

595f09d

Reuse trustedParents in looped calls to IsTrusted

5dd7da4

Update wallet_balance.py test to reflect new behavior

a550c58

Update comment in test/functional/wallet_balance.py

5ffe0d1

Co-Authored-By: MarcoFalke <falke.marco@gmail.com>

update variable naming conventions for IsTrusted

b49dcbe

Systematize style of IsTrusted single line if

8f174ef

Update release notes to mention changes to IsTrusted and impact on wa…

91f3073

…llet

Expand on wallet_balance.py comment from bitcoin#16766

4671fc3

JeremyRubin force-pushed the recursive-istrusted branch from 58cb227 to 4671fc3 Compare October 21, 2019 20:44

ryanofsky approved these changes Oct 22, 2019

View reviewed changes

ariard reviewed Oct 24, 2019

View reviewed changes

promag reviewed Nov 4, 2019

View reviewed changes

meshcollider merged commit 4671fc3 into bitcoin:master Nov 5, 2019

meshcollider removed this from Blockers in High-priority for review Nov 5, 2019

MarkLTZ mentioned this pull request Apr 4, 2020

Bitcoin PR tracking litecoinz-core/litecoinz#14

Closed

HashUnlimited pushed a commit to HashUnlimited/chaincoin that referenced this pull request Apr 17, 2020

Expand on wallet_balance.py comment from bitcoin#16766

8410c1f

JeremyRubin mentioned this pull request Apr 15, 2021

Implement BIP-119 Validation (CheckTemplateVerify) #21702

Closed

bitcoin locked as resolved and limited conversation to collaborators Dec 16, 2021

		@@ -112,10 +112,10 @@ def run_test(self):
		def test_balances(*, fee_node_1=0):

wallet: Make IsTrusted scan parents recursively #16766

wallet: Make IsTrusted scan parents recursively #16766

Conversation

JeremyRubin commented Aug 30, 2019 • edited

JeremyRubin commented Aug 30, 2019

DrahtBot commented Aug 30, 2019 • edited

Conflicts

maflcko commented Sep 3, 2019

JeremyRubin commented Sep 3, 2019

maflcko left a comment

Choose a reason for hiding this comment

JeremyRubin commented Sep 5, 2019

jonatack left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

promag commented Sep 6, 2019

JeremyRubin commented Sep 6, 2019

promag left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

luke-jr commented Sep 20, 2019

JeremyRubin commented Sep 21, 2019

fjahr commented Oct 1, 2019

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ryanofsky left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

JeremyRubin commented Oct 21, 2019

JeremyRubin commented Oct 21, 2019

ryanofsky left a comment • edited

Choose a reason for hiding this comment

ariard left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ariard Oct 25, 2019 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ariard commented Oct 25, 2019

fjahr commented Oct 30, 2019

promag left a comment

Choose a reason for hiding this comment

meshcollider commented Nov 5, 2019

ryanofsky commented Nov 5, 2019

JeremyRubin commented Aug 30, 2019 •

edited

DrahtBot commented Aug 30, 2019 •

edited

ryanofsky left a comment •

edited

ariard Oct 25, 2019 •

edited